package sort;

/**
 * @description: 插入排序（n2）
 * @title: InsertionSort
 * @author: zp
 * @date: 2021/11/15 20:21
 */
public class InsertionSort extends BaseSort {
    public static void main(String[] args) {
        int count = 100000;
        Integer[] ints = new Integer[count];
        for (int i = 0; i < count; i++) {
            ints[i] = (int) (Math.random() * count);
        }
        long start = System.currentTimeMillis();
        sort(ints);
        long end = System.currentTimeMillis();
        System.out.println((end - start));
    }

    public static void sort(Comparable[] a) {
        int n = a.length;
        //把数组近似看成两个 a1数组添加一个（有序的） a2数组是n-1个元素 然后从a2取元素和a1中的元素比较 找到正确位置 慢慢的把元素移到a1数组这样整个数组就是有序的
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (less(a[j], a[j - 1])) {
                    exch(a, j, j - 1);
                }

            }
            //断言 校验数据是否有序
            assert isSorted(a, 0, i);
        }
        //断言 校验数据是否有序
        assert isSorted(a);
    }
}
